home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / C / Games / Arashi 1.1.1 / source code / For your think c folder / Sound Kit ƒ / Huffman.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-08-31  |  11.5 KB  |  552 lines  |  [TEXT/KAHL]
  1. /*/
  2.      Project Arashi: Huffman.c
  3.      Major release: Version 1.1d2, 9/5/95
  4.  
  5.      Last modification: Thursday, August 31, 1995, 1:27
  6.      Created: Saturday, October 6, 1990, 22:34
  7.  
  8.      Copyright © 1990-1995, Juri Munkki
  9. /*/
  10.  
  11. /*
  12. >>    This file contains compression routines for the sound
  13. >>    data of Project STORM. It uses the Huffman algorithm.
  14. */
  15.  
  16. #include "Huffman.h"
  17. #include "Shuddup.h"
  18. #include "asm.h"
  19. #include "LowMem.h"
  20.  
  21. Handle    PlainHand;        /*    Handle to contain uncompressed sounds.    */
  22. long    PlainSize;        /*    Size when uncompressed.                    */
  23.  
  24. int            MaxCodeLen;    /*    Longest binary coding used.                */
  25. long        MsgBitSize;    /*    Number of bits in the compressed data.    */
  26. Handle        MsgHand;    /*    Compressed data.                        */
  27. treenode    **QuickTable;    /*    Quick lookup table for uncompress.    */
  28.  
  29. treenode    Nodes[VALUES*2];    /*    Huffman encoding tree.            */
  30. treenode    *Sorted[VALUES];    /*    Table of remaining subtrees.    */
  31. int            UsedNodes;            /*    Number of nodes used.            */
  32. int            numsorted;            /*    Number of remaining subtrees.    */
  33.  
  34. /*    Prototypes:
  35. */
  36. treenode *GetSmallest(void);
  37. void CombineNode(treenode *node0, treenode *node1);
  38. void AssignCode(treenode *node, int len, long code);
  39. void DeriveSound(void);
  40. Handle    ReadDataFiles(long ftype);
  41.  
  42. /*
  43. >>    This routine writes the bit patterns in the compressed
  44. >>    form. It's fairly slow on 68000 and 68010 machines, but
  45. >>    works quickly on others.
  46. */
  47. void    OutputPhase()
  48. {
  49.     register    Handle    Outdata;
  50.     register    long    *OutP;
  51.     register    char    *SrcP;
  52.     register    long    bitpos,data;
  53.     register    long    bitwidth;
  54.     register    int        i;
  55.                 long    codes[VALUES];
  56.                 int        lens[VALUES];
  57.     
  58.     Outdata=GetResource(SKRESTYPE,SKHUFFMANN);
  59.  
  60.     SetHandleSize(Outdata,sizeof(long)*VALUES+(MsgBitSize+7)/8);    
  61.     if(!MemError())
  62.     {    OutP=(long *)*Outdata;
  63.         SrcP=*PlainHand;
  64.         for(i=0;i<VALUES;i++)
  65.         {    *OutP++=Nodes[i].freq;
  66.             codes[i]=Nodes[i].code;
  67.             lens[i]=Nodes[i].codelen;
  68.         }
  69.         bitpos=0;
  70.         
  71.         if(LMGetCPUFlag()<2)    /*    Incredibly slow version for 68000 & 68010 processors.    */
  72.         {    while(bitpos<MsgBitSize)
  73.             {    data=codes[*SrcP];
  74.                 i=lens[*SrcP++];
  75.                 bitwidth = 1L <<(i-1);
  76.                 
  77.                 while(i--)
  78.                 {    if(data & bitwidth)    BitSet(OutP,bitpos++);
  79.                     else                BitClr(OutP,bitpos++);
  80.                     data <<= 1;
  81.                 }
  82.             }
  83.         }
  84.         else            /*    Much faster version for real processors...            ;-)    */
  85.         {    while(bitpos<MsgBitSize)
  86.             {    data=codes[*SrcP];
  87.                 bitwidth=lens[*SrcP++];
  88.                 asm    68020
  89.                     {    BFINS    data,(OutP){bitpos:bitwidth}
  90.                         add.l    bitwidth,bitpos
  91.                     }
  92.             }
  93.         }
  94.     }
  95.     else
  96.         DebugStr("\PHuffmann failed");
  97.     ChangedResource(Outdata);
  98.     WriteResource(Outdata);
  99. }
  100.  
  101. /*
  102. >>    GetSmallest returns the subtree with the
  103. >>    lowest frequency count. It is used to find
  104. >>    the two lowest counts that are to be combined
  105. >>    into a new subtree.
  106. */
  107. treenode    *GetSmallest()
  108. {
  109.     register    int            i;
  110.     register    int            small;
  111.     register    long        freq;
  112.     register    treenode    *found;
  113.     
  114.     i=small=numsorted-1;
  115.     freq=Sorted[numsorted-1]->freq;
  116.  
  117.     while(i--)
  118.     {    if(Sorted[i]->freq<freq)
  119.         {    small=i;
  120.             freq=Sorted[i]->freq;
  121.         }
  122.     }
  123.     found=Sorted[small];
  124.     Sorted[small]=Sorted[--numsorted];
  125.     return    found;
  126. }
  127. /*
  128. >>    Create a new node out of the two nodes (subtrees)
  129. >>    that are given as parameters.
  130. */
  131. void    CombineNode(node0,node1)
  132. treenode    *node0,*node1;
  133. {
  134.     register    treenode    *newnode;
  135.     
  136.     newnode=&Nodes[UsedNodes++];
  137.     newnode->value=0xFF;
  138.     newnode->codelen=0;
  139.     newnode->code=0;
  140.     newnode->freq=node0->freq+node1->freq;
  141.     newnode->zeroptr=node0;
  142.     newnode->oneptr=node1;
  143.     newnode->typeflag=-1;
  144.     
  145.     Sorted[numsorted++]=newnode;
  146. }
  147. /*
  148. >>    Recursively assigned a binary code
  149. >>    pattern to all nodes. (This is the
  150. >>    final step of the stage that determines
  151. >>    the encoding.)
  152. */
  153. void    AssignCode(node,len,code)
  154. treenode    *node;
  155. int            len;
  156. long        code;
  157. {
  158.     node->code=code;
  159.     node->codelen=len;
  160.     
  161.     if(node->typeflag)
  162.     {    AssignCode(node->zeroptr,len+1,code*2);
  163.         AssignCode(node->oneptr,len+1,code*2+1);
  164.     }
  165.     if(len>MaxCodeLen)
  166.         MaxCodeLen=len;
  167. }
  168. /*
  169. >>    The sound samples are run through this
  170. >>    filter before they are packed. Packing
  171. >>    the differences makes Huffman encoding
  172. >>    much more efficient.
  173. */
  174. void    DeriveSound()
  175. {
  176.     register    long    i;
  177.     register    char    *p;
  178.     register    char    delta,val;
  179.  
  180.     p=*PlainHand;
  181.     for(i=PlainSize;i;i--)
  182.     {    *p= (*p >> DROPBITS) & ANDMASK;
  183.         p++;
  184.     }
  185.  
  186.     p=*PlainHand;
  187.     delta=128>>DROPBITS;
  188.     for(i=PlainSize;i;i--)
  189.     {    val=*p;
  190.         *p++=(val-delta) & ANDMASK;
  191.         delta=val;
  192.     }
  193.     
  194. }
  195. /*
  196. >>    Build a tree out of the frequency
  197. >>    counts. This routine is used for
  198. >>    packing and unpacking of data.
  199. */
  200. void    HuffmannTree()
  201. {
  202.     register    long        i;
  203.     register    treenode    *small1,*small2;
  204.  
  205.     /*    Create pointers for used nodes.
  206.     */
  207.     numsorted=0;
  208.     for(i=0;i<VALUES;i++)
  209.     {    if(Nodes[i].freq)
  210.         {    Sorted[numsorted++]=&Nodes[i];
  211.         }
  212.     }
  213.     
  214.     /*    Huffmann tree generation.
  215.     */
  216.     while(numsorted>1)
  217.     {    small1=GetSmallest();
  218.         small2=GetSmallest();
  219.         CombineNode(small1,small2);
  220.     }
  221.  
  222.     /*    Assign bit strings to tree nodes.
  223.     */
  224.     MaxCodeLen=0;    
  225.     AssignCode(Sorted[0],0,0);
  226.     
  227.     /*    Calculate useful statistics.
  228.     */
  229.     MsgBitSize=0;    /*    Size of output in bits.                    */
  230.     for(i=0;i<VALUES;i++)
  231.     {    MsgBitSize+=Nodes[i].freq*Nodes[i].codelen;
  232.     }
  233. }
  234. /*
  235. >>    Compress the sound files in the current
  236. >>    directory and store the compressed data
  237. >>    in a pair of resources.
  238. */
  239. void    DoCompress()
  240. {
  241.     register    long        i,j;
  242.     register    char        *p;
  243.     
  244.     /*    First, read the data from disk:
  245.     */
  246.     PlainHand=ReadDataFiles(SOUNDFILE);
  247.     PlainSize=GetHandleSize(PlainHand);
  248.     HLock(PlainHand);
  249.  
  250.     /*    Do a delta operation on the sound and divide by 2.
  251.     */
  252.     DeriveSound();
  253.  
  254.     /*    Initialize node values.
  255.     */
  256.     for(i=0;i<VALUES;i++)
  257.     {    Nodes[i].value=i;
  258.         Nodes[i].codelen=0;
  259.         Nodes[i].code=0;
  260.         Nodes[i].freq=0;
  261.         Nodes[i].zeroptr=0;
  262.         Nodes[i].oneptr=0;
  263.         Nodes[i].typeflag=0;
  264.     }
  265.  
  266.     /*    Make a frequency count.
  267.     */
  268.     p=*PlainHand;
  269.     for(i=PlainSize;i;i--)
  270.     {    Nodes[*p++].freq++;
  271.     }
  272.     UsedNodes=VALUES;
  273.  
  274.     /*    Frequency plot in window.
  275.     */    
  276.     for(i=0;i<VALUES;i++)
  277.     {    j=200-(Nodes[i].freq*1000)/PlainSize;
  278.         MoveTo(i,j);
  279.         LineTo(i,j);
  280.     }
  281.  
  282.     /*    Generate the tree and bit strings.
  283.     */
  284.     HuffmannTree();
  285.  
  286.     if(MaxCodeLen<=32)
  287.     {    OutputPhase();
  288.     }
  289.     else
  290.     {    SysBeep(10);    /*    This should never happen.    */
  291.         DebugStr("\PHuffmann failed.");
  292.     }
  293.     HUnlock(PlainHand);
  294.     DisposHandle(PlainHand);
  295. }
  296. /*
  297. >>    DeCompress only handles the more generic part
  298. >>    of the sound decompression. It reads the packed
  299. >>    data and frequency counts. The frequency counts
  300. >>    are used to rebuild the same tree that was used
  301. >>    for compression. A fast lookup table is then
  302. >>    built so that multiple bits can be decoded at
  303. >>    once.
  304. */
  305. void    DeCompress()
  306. {    
  307.     register    long    *MsgPtr;
  308.     register    long    i,j;
  309.             treenode    *TheNode;
  310.  
  311.     QuickTable=(treenode **)NewPtr(sizeof(treenode)*(1<<QTBITS));
  312.     MsgHand=GetResource(SKRESTYPE,SKHUFFMANN);
  313.     HLock(MsgHand);
  314.     MsgPtr=(long *)*MsgHand;
  315.     
  316.     PlainSize=0;
  317.     /*    Initialize node values.
  318.     */
  319.     for(i=0;i<VALUES;i++)
  320.     {    Nodes[i].value=i;
  321.         Nodes[i].codelen=0;
  322.         Nodes[i].code=0;
  323.         Nodes[i].freq=*MsgPtr++;
  324.         Nodes[i].zeroptr=0;
  325.         Nodes[i].oneptr=0;
  326.         Nodes[i].typeflag=0;
  327.         
  328.         PlainSize+=Nodes[i].freq;
  329.     }
  330.     UsedNodes=VALUES;
  331.  
  332.     /*    Generate the tree and bit strings.
  333.     */
  334.     HuffmannTree();
  335.  
  336.     /*    Set up a table for quick access for the QTBITS first levels
  337.     **    of the tree.
  338.     */
  339.     for(i=0;i<(1<<QTBITS);i++)
  340.     {    QuickTable[i]=0;
  341.     }
  342.     for(i=UsedNodes;i>=0;i--)
  343.     {    if(Nodes[i].freq && Nodes[i].codelen<=QTBITS)
  344.         {    QuickTable[Nodes[i].code<<(QTBITS-Nodes[i].codelen)]=&Nodes[i];
  345.         }
  346.     }
  347.  
  348.     for(i=0;i<(1<<QTBITS);i++)
  349.     {    if(QuickTable[i])        TheNode=QuickTable[i];
  350.         else                    QuickTable[i]=TheNode;
  351.     }
  352.     
  353. }
  354. /*
  355. >>    This routine first runs the previous one
  356. >>    and then uses the tree and the lookup table
  357. >>    to decode the data. Every sound is also
  358. >>    processed so that it can be efficiently
  359. >>    played with the sound kit.
  360. */
  361. void    DecodeSounds()
  362. {
  363.                 Handle        sinfo;
  364.                 Ptr            sdatap;
  365.                 long        *infop;
  366.                 int            i;
  367.  
  368.                 treenode    **QTable;
  369.     register    treenode    *TheNode;
  370.     register    Ptr            MsgData;
  371.  
  372.     register    long        bitpos,data;
  373.     register    long        count;
  374.     register    char        delta;
  375.     register    long        len;
  376.  
  377.                 int            sampleframes;
  378.                 int            samplepad;
  379.  
  380.     
  381.     if(OldSound)            /*    The sounds are padded so that they in samplepad-sized packets.    */
  382.     {    sampleframes=185;    /*    Each packet contains samplesframes bytes of data.                */
  383.         samplepad=188;
  384.     }
  385.     else
  386.     {    sampleframes=512;    /*    If the sound manager is used, no padding is necessary, but the    */
  387.         samplepad=512;        /*    sound length has to be a multiple of 512.                        */
  388.     }
  389.  
  390.     QTable=QuickTable;
  391.  
  392.     sinfo=GetResource(SKRESTYPE,SKSTABLE);
  393.     NumSounds=GetHandleSize(sinfo)/sizeof(long);
  394.     HLock(sinfo);
  395.     infop=(long *)*sinfo;
  396.  
  397.     len=0;
  398.     for(i=0;i<NumSounds;i++)
  399.     {    len+=((infop[i]+(sampleframes-1))/sampleframes)*samplepad;
  400.     }
  401.     
  402.     HUnlock(MsgHand);
  403.  
  404.     SKPtr=NewPtr(len+sizeof(SoundStuff)*(long)NumSounds);
  405.     if(MemError())
  406.     {    NumSounds=0;
  407.         return;
  408.     }
  409.  
  410.     HLock(MsgHand);
  411.     MsgData=(sizeof(long)*VALUES)+*MsgHand;
  412.  
  413.     Sounds=(void *)SKPtr;
  414.     sdatap=SKPtr+sizeof(SoundStuff)*(long)NumSounds;
  415.     
  416.     for(i=0;i<NumSounds;i++)
  417.     {    len=((infop[i]+(sampleframes-1))/sampleframes)*samplepad;
  418.         Sounds[i].Poin=sdatap;
  419.         Sounds[i].Len=len;
  420.         Sounds[i].Count=len/samplepad;
  421.         sdatap+=len;
  422.     }
  423.  
  424.     delta=128>>DROPBITS;
  425.     bitpos=0;
  426.  
  427.     for(i=0;i<NumSounds;i++)
  428.     {    sdatap=Sounds[i].Poin;
  429.         len=infop[i];
  430.         count=sampleframes;
  431.  
  432.         if(LMGetCPUFlag()<2)        /*    Check for processor type.                */
  433.         {    while(len--)    /*    Version for 68000 and 68010 processors.    */
  434.             {
  435.                 asm
  436.                     {    cmp.b    #16,bitpos
  437.                         blt.s    @nobitshift
  438.                         sub.b    #16,bitpos
  439.                         lea        2(MsgData),MsgData
  440.                     @nobitshift
  441.                         move.l    (MsgData),data
  442.                         move.l    bitpos,D0
  443.                         add.b    #QTBITS,D0
  444.                         rol.l    D0,data
  445.                         and.l    #((1<<QTBITS)-1),data
  446.                     }
  447.                     TheNode=QTable[data];
  448.     
  449.                 if(TheNode->typeflag)
  450.                 {    bitpos+=QTBITS;
  451.                     asm    {
  452.                     @begin0        cmp.b    #16,bitpos
  453.                                 blt.s    @nobitshifteither
  454.                                 sub.b    #16,bitpos
  455.                                 lea        2(MsgData),MsgData
  456.                     @nobitshifteither
  457.                                 move.l    (MsgData),data
  458.                                 addq.l    #1,bitpos
  459.                                 rol.l    bitpos,data
  460.                                 bcc.s    @zeropoint0
  461.                             
  462.                                 move.l    OFFSET(treenode,oneptr)(TheNode),TheNode
  463.                                 move.w    OFFSET(treenode,typeflag)(TheNode),D0
  464.                                 bne.s    @begin0
  465.                                 bra.s    @loopdone0
  466.                     @zeropoint0    move.l    OFFSET(treenode,zeroptr)(TheNode),TheNode
  467.                                 move.w    OFFSET(treenode,typeflag)(TheNode),D0
  468.                                 bne.s    @begin0
  469.                     @loopdone0        
  470.                     }
  471.                 }
  472.                 else
  473.                 {    bitpos+=TheNode->codelen;
  474.                 }
  475.                 delta+=TheNode->value;
  476.                 delta&=ANDMASK;
  477.                 *sdatap++=delta;
  478.                 if(!--count)
  479.                 {    count=samplepad-sampleframes;
  480.                     while(count--)
  481.                         *sdatap++=delta;
  482.     
  483.                     count=sampleframes;
  484.                 }
  485.             }
  486.             
  487.             if(count!=sampleframes)
  488.             {    count=(count+samplepad-sampleframes) % samplepad;
  489.                 while(count--)
  490.                 {    *sdatap++=delta;
  491.                 }
  492.             }
  493.         }
  494.         else    /*    Version for 68020, 68030, 68040 processors    */
  495.         {    while(len--)
  496.             {
  497.                 asm    68020
  498.                     {
  499.                     bfextu    (MsgData){bitpos:QTBITS},data
  500.                     }
  501.                     TheNode=QTable[data];
  502.     
  503.                 if(TheNode->typeflag)
  504.                 {    bitpos+=QTBITS;
  505.                     asm    68020
  506.                     {
  507.                     @begin
  508.                                 bfextu    (MsgData){bitpos:1},data
  509.                                 beq.s    @zeropoint
  510.                                 move.l    OFFSET(treenode,oneptr)(TheNode),TheNode
  511.                                 addq.l    #1,bitpos
  512.                                 move.w    OFFSET(treenode,typeflag)(TheNode),D0
  513.                                 bne.s    @begin
  514.                                 bra.s    @loopdone
  515.                     @zeropoint    move.l    OFFSET(treenode,zeroptr)(TheNode),TheNode
  516.                                 addq.l    #1,bitpos
  517.                                 move.w    OFFSET(treenode,typeflag)(TheNode),D0
  518.                                 bne.s    @begin
  519.                     @loopdone        
  520.                     }
  521.                 }
  522.                 else
  523.                 {    bitpos+=TheNode->codelen;
  524.                 }
  525.                 delta+=TheNode->value;
  526.                 delta&=ANDMASK;
  527.                 *sdatap++=delta;
  528.                 if(!--count)
  529.                 {    count=samplepad-sampleframes;
  530.                     while(count--)
  531.                         *sdatap++=delta;
  532.     
  533.                     count=sampleframes;
  534.                 }
  535.             }
  536.             
  537.             if(count!=sampleframes)
  538.             {    count=(count+samplepad-sampleframes) % samplepad;
  539.                 while(count--)
  540.                 {    *sdatap++=delta;
  541.                 }
  542.             }
  543.         }
  544.     }
  545.     
  546.     HUnlock(sinfo);
  547.     ReleaseResource(sinfo);
  548.     HUnlock(MsgHand);
  549.     ReleaseResource(MsgHand);
  550.     DisposPtr(QuickTable);    
  551. }
  552.